import java.util.Random;

public class Main {
    public static void main(String[] args) {
        /**
         * 手写实现三路快排*/
        Main o = new Main();
        int[] nums = new int[]{9,5,2,1};
        quickSort(0, nums.length-1, nums);
        for(int e: nums) {
            System.out.print(e + " ");
        }
    }

    public static void quickSort(int left, int right, int[] nums) {
        /**
         * 三路快排递归实现快排-排升序*/
        // 1 递归出口
        if(left >= right) {
            return;
        }

        // 2 三路快排
        // -1 随机设置基准值
        int key = nums[left + new Random().nextInt(right - left + 1)];
        int i = left;
        int l = left-1;
        int r = right+1;
        while(i < r) {
            if(nums[i] < key) {
                swap(i++, ++l, nums);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(i, --r, nums);
            }
        }

        // 3 递归
        quickSort(left, l, nums);
        quickSort(r, right, nums);
    }

    public static void swap(int left, int right, int[] nums) {
        /**
         * 用于交换数组中两个元素的值*/
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
